# Full text of "Technical Report 10 (1998)"

## See other formats

Technical report # 10 by Kittisak Tiyapan Tokyo Institute of Technology 25 July 1998 1 Supported by the Ministry of Education of Japan Technical report #10, by Ixittisak Tiyapan 1 Contents Introduction. 2 Critical probability in traffic modelling and control. 2 abstract. 2 Introduction. 2 Theory. 2 Traffic Modelling. 2 Traffic Control. 3 Conclusion. 3 Modelling of Traffic Congestion. 4 abstract. 4 Introduction. 4 Theory. 5 Algorithm. 9 Examples . 9 conclusion. 9 List of Figures 1 Procedure for finding the critical parameter of a traffic networks . 12 2 Diagram representing a traffical networks of City X . 13 3 Diagram representing a traffical networks of City X after the addition of a ring-road. 13 4 Traffic control scheme for City X . 14 5 The dark line shown in (a) is a road while that shown in (b) is not . 14 6 The road portrayed is congested whenever no cars could enter it from any of the five adjacent roads . 15 7 (a) is considered to be the same as (b) . 15 8 The case where Pc < 0.5. Here a is the situation where cars have not yet percolated; b is that where cars have percolated; c is that where space has percolated and d is that where space has not yet percolated . 16 9 The case where Pc = 0.5. 17 10 The case where Pc > 0.5. 18 11 The case where Pc = 0.5. 18 12 The case where Pc > 0.5. 18 13 Algorithm for finding a bond percolation . 19 14 Bangkok’s traffic percolation simulation . 20 15 Bangkok’s inner city traffic percolation simulation . 20 2 Report in Systems and Control, Tokyo Institute of Technology Introduction Critical probability in traffic modelling and control abstract Percolation has been playing a big role in many fields of Physics, Chemistry as well as Forestry and Biology. But upto this time its application to traffic modelling and control has not been mentioned in existing literature, contrary to its inherently similar in nature to the field. This work is an attempt to introduce it to this application. Introduction Percolation says that for any kind of networks of connections among components, namely vertices and bonds, there is one parameter with its own unique value which could be different from other or other kind of networks. This parameter is named the percolation probability or the critical probability. This critical probability or p c marks the transition from one of the two phases into another. Theory In order to be succinct, only one theorem will be briefly mentioned. Theorem 1 For any traffic networks the state of traffic at any moment can be described as being in one of the three states namely, free-flowing, congested or stand-still. Furthermore, the free- flowing case corresponds to the case where p < min(l —p c ), the congested case to the case where min ((1 — p c ), Pc) < p < max (1 — p c ), (p c ) and the stand-still case to p > max (1 — p c ), ( p c )■ Proof. From percolation theory we know that there exists 0 < p c < 1 for any networks. Obviously p c can only have have a value within one of these three intervals, that is < 0.5, = 0.5 or > 0.5. Furthermore we may consider the percolation as being percolation of flowing roads as well as the percolation of jammed roads. Our interval from 0 to 1 can then be divided into three sections namely, 0 < p < min (1 — p c ), min ((1 — p c ), Pc) < p < max (1 — p c ) , ( p c ) and max (1 — p c ) , ( p c ) < p < 0. The first one of the three intervals above corresponds to the situation where cars have not yet percolate while space has. And thus it corresponds to the free-flowing traffic. The next one corresponds either to the situation where both cars and space has percolated or to the situation where neither has percolated depending on whether p c < 0.5 or p c > 0.5 originally. And thus it corresponds to the congested traffic. And the last one corresponds to the situation where cars have percolated while space has not and therefore to the stand-still traffic. The case where p c = 0.5 is a special case where the second one of the three intervals considered vanishes.© Traffic Modelling For modelling purpose the percolation probability of the networks being considered is obtained by using the procedure shown in Figure 1. The structures of the data mentioned in Figure 1 are given below. Technical report #10, by Kittisak Tiyapan 3 Data Structure 1 Junction Data in file named Junction. 3 datasets per record. J the number assigned to this junction, of type H + . x x-coordinate of this junction, of type IR + . y y-coordinate of this junction, of type IR + . Data Structure 2 Road Data in file named Road. 3 datasets per record. R the number assigned to this road, of type I + . i the number of the junction at one end of this road, of type I + . j the number of the junction at the other end of this road, of type H + . Data Structure 3 Cluster C the number assigned to this cluster, of type I + . n the amount of roads belonging to the cluster, of type I + . / the fractal dimension of the cluster, IR + . M set of member roads of this cluster, M = {mi : mi G (cluster Cfmt G IR, i = 1,... , n}. For illustrative purpose a network of an imaginary city called City X is considered in Figure 2 and Figure 3. Figure 3 is that of the networks in Figure 2 after the construction of a ring road. The percolation probability of the networks shown in Figure 2 was found to be approximately 0.75, averaged over 20 simulations. The percolation probability of the networks shown in Figure 3 was found to be approximately 0.72, averaged over 20 simulations. That is the addition of the ring road reduced the p c . The results shows that the ring road added resulted in the reduction of the p c . And since the p c of this network is > 0.5 this also resulted in the reduction of the probability that this network will be in a congested situation. Traffic Control Let S be the situation where the percolation of roads where traffics are flowing occurs. S is namely space percolation. And let 77 be the situation where the percolation of congested roads occurs. H is namely car percolation. The decisional cases in Figure 4 are cases where (S A ->77), (S' A 77) V (-■S A — >77) and (-iS 1 A 77) for cases number 1, 2 and 3 respectively. The parameter A in Figure 4 is the sampling time of the data. A could be approximately 5 minutes. Conclusion I hope that this work has showed the possibility of applying the percolation theory to modelling and control problems of traffic networks. More work is still needed to be done in order to deliberate upon this idea. It is important to note also that this approach, if turned out to be feasible, could be similarly applied to fields where other kinds of traffic are concerned too, to mention but one of such fields is the traffic inside the Internet. 4 Report in Systems and Control, Tokyo Institute of Technology Modelling of Traffic Congestion abstract Bad traffic conditions could have adverse effects on a country’s economics and well-beings. News of such devastating situations as a traffical stand-still means reduced competitive edges for a de- vclopping country, discouraged tourists and an enormous amount of wasted resources. Percolation theory has long been associated with similar problems occuring in other areas of science, for exam¬ ple sieve-blinding and filtration. These problems essentially deals with the flow of fluids through a media which has random structure and, when the media is subjected to blockages. Similar to how a filter media can be classified according to the way it behaves at the onset of percolation, any traffical networks could be distinguished from the others by its ability to withstand heavy traffic conditions before a stand-still occurs. This work is the beginning of an attempt to model traffical networks with the idea of percolation in mind. It has been proposed here that a traffical networks can either be excellent at tolerating a stand-still or, it can boast that it rarely finds itself congested, but never both at the same time. It has been proposed that a trade-off has to be made if one were to design a new traffical networks. Introduction There are two kinds of lattices or tessellations. One is regular and the other random. Examples of regular tessellations are honeycomb and Kagome lattices in 2-dimension and hexagonal tessellations in 3-dimension. Tessellations which are not regular are random [CN88, MC89, HS95]. There are random tessellations with underlying rules as a Vorono’i tessellations [Boo87, Muc96, RHOG88]. Examples of these rule-specific random tesselations are patterns of cells in living tissue and structure of the universe [vdW94], An example of these purely-random tessellations is a traffical networks. Critical probability [JG96, Cha96, JG95] is a property which has long been associated with the study of tessellations’ properties. This value is characteristic for each type of tessellations concerned and is closely related to the coordination number of the tessellations or, in the random tessellations case, the average coordination number. For all kind of tessellations finding the critical probability can be done by doing simulations. Theoretical computation [SK71] of exact values of crical probabilities is also possible but, only for certain types of regular tessellations. So for traffic networks the only two possible ways of finding the critical probability for a network of a certain city are by doing simulations on computer and, by approximating the value from the average coordination number of the network. Topics related to traffic congestions and the states of congestion have been discussed in existing literatures [SAH97, Sis97, HW97]. In this work it has been proposed for a traffical networks of a specific city that, once the number of roads experiencing a stoppage reaches a certain value the whole city will come to a stand-still. It has also been further proposed that, in the designing of a traffical networks a trade-off has to be made between robustness to congestions and robustness to stand-stills. This means that we can have a traffic networks which is most of the time congested but never comes to an overall stand-still or, we can have a traffic networks which is most of the time flowing freely until the amount of cars increases causing it to come to an overall stand-still, but we can not have a kind of traffic networks which is free-flowing all the time and never experience a stand-still. Technical report #10, by Kittisak Tiyapan 5 Study of traffic networks based on queueing theory also categorizes traffic into several states [Leu88] but, the definitions of these states are quite different from those here. Theory This section is organized as a number of definitions leading to main theorems. These definitions are good because they serve as definitive description to the problem as well as aid for writing a program for doing simulation. Definition 1 A network is the linkages of vertices by bonds and has bond percolation proba¬ bility and vertex percolation probabability as its two invariances. A network will be denoted by Nwk(Vtx, Bnd, Pytx!-P Bn d) where Vtx, Bnd C IN + {+oo}, Py tx , Pu n d £ IR, 0 < Py tx < 1 a nd 0 < -PBnd < 1- Definition 2 Nwk( Bnd) represents a network which is considered as connections of bonds at ver¬ tices while Nwk( Vtx) represents a network which is considered as connections of vertices by bonds. Definition 3 Bnd(V) represents a set of all the bonds which are connected to v Wv E V V C Vtx. Similarly Vtx(P) represents a set of all the vertices which are connected to b \/b G B B C Bnd. Definition 4 A bond can have either of the two states which are called free fBnd 0 ,) or blocked fBnd 1 ,). Likewise a vertex can be either free (Vtx 0 ) or occupied (Vtx 1 ). Definition 5 A cluster is a set of either of the two components of a network, namely vertices and bonds, with each one of its members connecting to some other members. There are clusters of bonds represented by { Cl( Bnd) : Vq G Cl(Bnd)36 2 € Cl(Bnd) s.t. Vtx(6 x ) = Vtx(62) Cl(Bnd) C Bnd} (1) and there are clusters of vertices represented by {Cl(Vtx) : Viq G Cl(Vtx)3u 2 G Cl( Vtx) s.t. Bnd(iq) = Bnd(u2) Cl(Vtx) C Vtx}. (2) Definition 6 The set of all the clusters (of either bonds or vertices) is { Tcl(-) : Cl(-) C Nwk(-) <=► Cl(-) G Td(-)}, (3) where ■ is either Bnd or Vtx. Definition 7 Each cluster has a definite size which is the number of either bonds or vertices com¬ prising it, depending on whether the cluster is a cluster of bonds or a cluster of vertices. This size is represented by Size(Cl) Cl G IN + {+oo} (4) Definition 8 The width of a cluster is the dimension of the cluster in either x- or y-axis and, is represented by Width( Cl) G IR Cl G IN + {+oo} ( 5 ) 6 Report in Systems and Control, Tokyo Institute of Technology Definition 9 The largest cluster (of either bonds or vertices) of any network is { Mcl(-) : Size( Mcl) = sup( Size( Cl)) V Cl G Tel} . (6) Definition 10 The percolating cluster of any network is { Pclust(-) : Pclust(-) = Mcl Mcl(-) — > oo as Size(Nwk(-)) —> oo} . (7) While the smallest percolating cluster possible for any network is Inf(-) = inf( Pclust) (8) Definition 11 The percolating cluster of a traffical network is { Pcl( Bird) : Pcl( Bnd) = Cl( Bnd) Width( Cl( Bnd)) = Width( Nwk( Bnd))} (9) Definition 12 For any network a critical probability is {PeH-P = MC(.,= M(.)}. (10) While Pc( Bnd) is its bond critical probablity and Pc( Vtx) is its vertex critical probability. Definition 13 For a traffical network a critical probability is { PC < B " d > : PC <'> = ^WNwklBiy” Md < B " d > = Pd < Bnd >) - < U > Definition 14 A free-flowing network is | Nwk : 3 Pcl( Nwk( Bnd 0 )) Pcl( Nwk( Bnd 1 ))} . (12) A stand-still is | Nwk : jB Pcl( Nwk( Bnd 0 )) 3 Pcl( Nwk( Bnd 1 ))} . (13) A congested network is | Nwk : | jB Pcl( Nwk( Bnd 0 )) Pcl( Nwk( Bnd 1 ))} 0 (14) {3 Pcl( Nwk( Bnd 0 )) 3 Pcl( Nwk( Bnd 1 ))}} . The following definitions concern with features found in typical traffical networks. Definition 15 A road is a single bond. It can be either a one-way or a two-way street but, without any branching along its length. The only two opennings are located at both ends. Definition 16 At any instance a road is said to be congested when no cars could enter it. Definition 17 A round-about is considered simply as being a vertex. Technical report #10, by Kittisak Tiyapan 7 Definition 18 Let p = then ’ Frf(Nwk(Bnd)) = (Nwk(Bnd) [0, min(Pc, 1— Pc))}, (15) Cgd( Nwk( Bnd)) = { Nwk( Bnd) : p G [min( Pc, 1 — Pc), max( Pc, 1 — Pc)]} , (16) and, Stp( Nwk( Bnd)) = { Nwk( Bnd) : p G (max( Pc, 1 - Pc), 1]} . (17) Theorem 2 For a traffical network. Pc(Bnd°) = Pc(Bnd 1 ), (18) where Bnd 0 is a free bond or a non-congested road and, Bnd 1 is an occupied bond or a congested road. Proof The networks remains the same whether one consider it as a network of free roads or, that of congested roads. In other words, Nwk(Bnd°) = Nwk(Bnd 1 ) = Nwk(Bnd) When Mcl(Bnd°)= Pcl(Bnd°), Pel Bnd 0 ) — ^ vcl ( Bnd °) eTcl Size( Cl( Bnd 0 )) Cl 11 ’ ~ Size( Nwk( Bnd 1 )) While when Mc^Bnd 1 ) = Pc^Bnd 1 ), p r /p nr ip - ^VGHBnddeTci Size( Cl( Bnd 1 )) 1 Size( Nwk( Bnd 0 )) (19) ( 20 ) ( 21 ) Now suppose instead of starting from Nwk( Bnd 0 ) and keep adding Bnd 1 randokmly until Mcl( Bnd 1 ) Pci (Bnd 1 ), we could have said from the start that we wer looking at Nwk(Bnd 1 ) and added Bnd 0 randomly until Mcl(Bnd°) = Pcl(Bnd°). From this reasoning Mcl( Bnd 1 ) = Pcl( Bnd 1 ) = Pcl(Bnd°) = Mcl(Bnd°). ( 22 ) From Equation 19 we have Size( Nwk( Bnd 0 )) = Size( Nwk( Bnd 1 )) = Size( Nwk( Bnd)). (23) Thus it follows from Equation 20 and Equation 21 that Pc(Bnd°) = Pc( Bnd 1 ). (24) QED. Report in Systems and Control, Tokyo Institute of Technology Theorem 3 For a traffical network, when Mcl( Bncl 1 ) = Pcl( Bncl 1 ) Pc( Bnd°) = P Bnd o EvcieTci Size(Cl(Bnd°)) Size( Nwk( Bnd)) (25) Proof When Mc^Bnd 1 ) = Pc^Bnd 1 ) we know from Equation 21 that p , p ,ix _ EvcKBnd^eTci Size( Cl( Bnd 1 )) 1 j “ Size( Nwk( Bnd 0 )) ' Now the only states possible for a Bnd are either Bnd(O) or Bnd(l). Thus ^ Size( Cl( Bnd 0 )) + ]T Size( Cl( Bnd 1 )) = Size( Nwk( Bnd)) V Cl( Bnd°)e Tel VC1( Bridge Tel or, Then ^ Size( Cl( Bnd 0 )) = Size(Nwk( Bnd)) — ^ Size( Cl( Bnd 1 )). VCl( Bnd°)e Tel VC1( Bnd^e Tel Pc( Bnd 0 ) = P Bnd o = Evci(Bnd°)eTci Size( Cl( Bnd 0 )) Size( Nwk( Bnd)) Size( Nwk( Bnd)) - EvcifBnd^eTd Size( Cl( Bnd 1 )) = 1 - Size( Nwk( Bnd)) Evci( Bnd 1 )^Tci Size(Cl(Bnd )) Size( Nwk( Bnd)) ' (26) (27) (28) (29) (30) (31) QED. Theorem 4 VNwk(Bnd) Frf( Nwk( Bnd)) is a free-flowing network, Cgd( Nwk( Bnd)) is a con¬ gested network and Stp( Nwk( Bnd)) is a stand-still. Proof Consider a traffical network with Pc < 0.5 first as Pc( Bnd 1 ) in Nwk( Bnd 0 ) and then, as Pc( Bnd 0 ) in Nwk(Bnd 1 ). This is shown in Figure 8. From Theorem 2 and Theorem 25 we have a = d and b = c in Figure 8. Then from Definition 18, Frf( Nwk( Bnd)) = { Nwk( Bnd) : p E [0, a)} , (32) Cgd( Nwk( Bnd)) = { Nwk( Bnd) : p G [a, 1 - a]} (33) and Stp( Nwk( Bnd)) = { Nwk( Bnd) : p e (1 - a, 1]} . (34) Then from Figure 8 Frf( Nwk( Bnd)) represents the situation where cars has not yet percolated while space has. From Definition 14 this represents a free-flowing network. Similarly Cgd( Nwk( Bnd)) represents that situation where both cars and space have percolated and, Stp( Nwk( Bnd)) that Technical report #10, by Kittisak Tiyapan 9 situation where only cars have percolated. From Definition 14, Cgd( Nwk( Bnd)) is a congested network and Stp( Nwk( Bnd)) a stand-still. Now proceed on in the same line as above for the case where Pc = 0.5 and that where Pc > 0.5 which are shown diagramatically respectively as Figure 9 and Figure 10. In the case represented by Figure 9 Definition 18 gives Frf( Nwk( Bnd)) = { Nwk( Bnd) : p e [0,0.5)} , (35) Cgd( Nwk( Bnd)) = { Nwk( Bnd) : p G [0.5, 0.5] or Pc = 0.5} (36) and Stp( Nwk( Bnd)) = { Nwk( Bnd) : p e (0.5,1]} . (37) And Definition 14 says that Frf( Nwk( Bnd)) is a free-flowing network, Cgd( Nwk( Bnd)) is a con¬ gested network and, Stp( Nwk( Bnd)) is a stand-still. The juxtaposition between the congestion of space and cars is shown in Table 11. And in the last case of Figure 10, Definition 18 again gives Equations 32, 33, and 34 while, Definition 14 again says that Frf(Nwk( Bnd)) is a free-flowing network, Cgd( Nwk( Bnd)) is a congested network and, Stp( Nwk( Bnd)) is a stand-still. The con¬ gestion of space and cars can then be shown in Table 12. QED. Algorithm The algorithm for finding the critical probability for a bond network is shown in the diagram in Figure 13. Examples This section shows the results of simulation on traffic networks. Both Figure 14 and Figure 15 are the traffic networks of Bangkok but larger area is covered by Figure 14. The critical probability obtained from simulations similar to these could be used to determine the states of traffic congestion of that city. Once the state of the traffic at any moment is known it will be possible control the traffic accordingly. For example, once the number of cars in any area has nearly reached the percolation threshold it would be wise to stop traffic going into that area until the density has somewhat been reduced. Another example is that when there are two or more neighbouring areas experiencing heavy congestion it would be good to manage the traffic in such a way that moves cars away from those streets between those area as well as away from those congested area. This is to prevent the congested areas from merging which could cause percolation. conclusion Like the formation of galaxies when primordial gas has density exceeding certain value, and many things analogous to this which are found in plenty in nature, traffic in any city will come to a stand-still once the number of conjested roads reaches a percolating value which is specific for each city. 10 Report in Systems and Control, Tokyo Institute of Technology Bibliography [Boo87] B. N. Boots. Edge length properties of random Vorono’i polygons. Metallography, 20(2):231-236, May 1987. [Cha96] L. Chayes. On the length of the shortest crosing in the super-critical phase of mandel- brot’s percolation. Stochastic Processes and their Applications, 61(1):25—43, 1996. [CN88] S. K. Chan and K. M. Ng. Geometrical characteristics of the pore space in a random packing of equal spheres. Powder Technology, 54(2):147—155, February 1988. [HS95] Lothar Heinrich and Eik Schule. Generation of the typical cell of a non-Poissonian Johnson-Mchl tessellation. Communications in Statistics. Stochastic Models, 11(3) :541 560, 1995. [HW97] Dwight A. Hennessy and David L. Wiesenthal. Relationship between traffic congestion, driver stress and direct versus indirect coping behaviours. Ergonomics, 40(3):348—361, March 1997. [JG95] Iwan Jensen and Anthony J. Guttmann. Series expansions of the percolation probability for directed square and honeycomb lattices. Journal of Physics A. Mathematical and General, 28(17):4813-4833, 1995. [JG96] Iwan Jensen and Anthony J. Guttmann. Series expansions of the percolation probability on the directed triangular lattice. Journal of Physics A. Mathematical and General, 29(3) :497 517, 1996. [Leu88] Wilhelm Leutzbach. Introduction to the theory of traffic flow. Springer-Verlag, 1988. [MC89] Peter Meer and Steven Connelly. Fast parallel method for synthesis of random patterns. Pattern recognition, 22(2):189-204, 1989. [Muc96] Lutz Muche. The Poison-Vorono’i tessellation. II edge length distribution functions. Mathematische - Nachrichten, 178:271-281, 1996. [RHOG88] R. Riedinger, M. Habar, P. Oelhafen, and H. J. Guntherodt. About the Delaunay- Voronoi tessellation. Journal of Computational Physics, 74(1) :61—72, 1988. [SAH97] Hanif D. Sherali, Namita Arora, and Antoine G. Hobeika. Parameter optimization methods for estimating dynamic origin-description trip-tables. Transportation Research, Part B: Methodological, 31B(2):141-157, April 1997. [Sis97] Virginia P. Sisiopiku. Congestion analysis of Southfield freeway - a case study. In Challenges, Innovations, and Opportunities Proceedings of the Conference on Traffic Congestion, pages 556-562, NY, 1997. ASCE. [SK71] Vinod K. S. Shante and Scott Kirkpatrick. An introduction to percolation theory. Adv. Phys., 20:325-357, 1971. Technical report #10, by Kittisak Tiyapan 11 [vdW94] Rien van de Weygaert. Fragmenting the universe III. the construction and statistics of 3-D Voronoi tessellations. Astronomy and Astrophysics , 283:361-406, 1994. 12 Report in Systems and Control, Tokyo Institute of Technology Figure 1: Procedure for finding the critical parameter of a traffic networks. Technical report #10, by Kittisak Tiyapan 13 CityX X city Figure 2: Diagram representing a traffical networks of City X. CityX X city Figure 3: Diagram representing a traffical networks of City X after the addition of a ring-road. 14 Report in Systems and Control, Tokyo Institute of Technology Figure 4: Traffic control scheme for City X. Figure 5: The dark line shown in (a) is a road while that shown in (b) is not. Technical report #10, by Kittisak Tiyapan 15 Figure 6: The road portrayed is congested whenever no cars could enter it from any of the five adjacent roads. Figure 7: (a) is considered to be the same as (b). 16 Report in Systems and Control, Tokyo Institute of Technology A 0 0.5 i 0 0.5 H=- d Figure 8: The case where Pc < 0.5. Here a is the situation where cars have not yet percolated; b is that where cars have percolated; c is that where space has percolated and d is that where space has not yet percolated. Technical report #10, by Kittisak Tiyapan 17 Figure 9: The case where Pc = 0.5. 18 Report in Systems and Control, Tokyo Institute of Technology a h=- b A 0 0.5 i B 0 0.5 i c d b=--4=--^ Figure 10: The case where Pc > 0.5. Intervals Cars percolation Space percolation Frf(-) N Y Cgd(-) Y Y Stp(-) Y N Figure 11: The case where Pc = 0.5. Intervals Cars percolation Space percolation Frf(-) N Y Cgd(-) N N Stp(-) Y N Figure 12: The case where Pc > 0.5. Technical report #10, by Kittisak Tiyapan 19 Figure 13: Algorithm for finding a bond percolation. 20 Report in Systems and Control, Tokyo Institute of Technology The percolating cluster Figure 14: Bangkok’s traffic percolation simulation. The percolating cluster Figure 15: Bangkok’s inner city traffic percolation simulation.